#include "ALGraph.h"
#include "Queue.h"
#include "exp_3.h"
//每学期的学分限制，授课门数上限，
float score_lim;
int num_lim;
int* inDegree;
Boolean* visited;
//层次数组
int* level;
//最优课表答案
Answer ans;
//临时答案
int* tmpAns;
//临时学期数组
int* tmpTerm;
void update(ALGraph* g) {
    int len = g->vexnum;
    // tmpAns数组的总教学时长
    int totalWeeks = 0;
    //当前层次，当前层次课程的最大周数，当前所在学期，当前学期的课程数目
    int i, curWeeks = g->Adjlist[tmpAns[0]].data.weeks, curTerm = 1, curNum = 1;
    tmpTerm[0] = 1;
    //当前学期学分
    float curScore = g->Adjlist[tmpAns[0]].data.score;
    for (i = 1; i < len; ++i) {
        //检查是否达到授课门数上限或学分上线
        if (curNum == num_lim ||
            curScore + g->Adjlist[tmpAns[i]].data.score > score_lim) {
            ++curTerm;
            totalWeeks += curWeeks;
            curWeeks = g->Adjlist[tmpAns[i]].data.weeks;
            curScore = g->Adjlist[tmpAns[i]].data.score;
            curNum = 1;
        }
        else { //还是同一个学期
            ++curNum;
            curScore += g->Adjlist[tmpAns[i]].data.score;
            if (level[tmpAns[i]] == level[tmpAns[i - 1]]) {
                //同时上的课，需要其最大周数
                if (g->Adjlist[tmpAns[i]].data.weeks > curWeeks) {
                    curWeeks = g->Adjlist[tmpAns[i]].data.weeks;
                }
            }
            else {
                //同时上的课结束，加到学时里
                totalWeeks += curWeeks;
                curWeeks = g->Adjlist[tmpAns[i]].data.weeks;
            }
        }
        tmpTerm[i] = curTerm;
    }
    //加上剩下没算进去的课时
    totalWeeks += curWeeks;
    //看看总教学时长是不是更小了
    if (totalWeeks <= ans.totalTerms) {
        //看看学期数是否更少
        if (tmpTerm[len - 1] < ans.totalTerms) {
            for (i = 0; i < len; ++i) {
                ans.course[i] = tmpAns[i];
                ans.term[i] = tmpTerm[i];
                ans.totalWeeks = totalWeeks;
                ans.totalTerms = curTerm;
                /*测试
                printf("%d(%d) ", tmpAns[i], tmpTerm[i]);
                */
            }
            /*测试
            printf("totalWeeks:%d\ttotalTerm:%d", totalWeeks, curTerm);
            */
        }
    }
}

void DFS(ALGraph* g, int pos) {
    int len = g->vexnum;
    int i;
    if (pos == len) {
        // tmpAns
        int tmp = 0;
        //所得拓扑序列层次需递增
        for (i = 0; i != len; ++i) {
            if (tmp < level[tmpAns[i]]) {
                tmp = level[tmpAns[i]];
            }
            else if (tmp > level[tmpAns[i]]) {
                return;
            }
        }
        //更新ans
        update(g);
        /*
        //测试代码
        printf("order:");
        for (int i = 0; i != len; ++i) {
            printf("%d ",tmpAns[i]);
        }
        printf("\nlevel:");
        for (int i = 0; i != len; ++i) {
            printf("%d ",level[ans.course[i]]);
        }
        putchar('\n');
        */
        return;
    }
    ArcNode* j;
    for (i = 0; i < len; ++i) {
        if (!inDegree[i] && !visited[i]) {
            for (j = g->Adjlist[i].firstarc; j != NULL; j = j->nextarc) {
                --inDegree[j->adjvex];
            }
            visited[i] = TRUE;
            tmpAns[pos] = i;
            DFS(g, pos + 1);
            //还原
            for (j = g->Adjlist[i].firstarc; j != NULL; j = j->nextarc) {
                ++inDegree[j->adjvex];
            }
            visited[i] = FALSE;
        }
    }
    return;
}

Boolean course_sort(ALGraph* g) {
    int i;
    int courseNum = g->vexnum;
    inDegree = (int*)malloc(sizeof(int) * courseNum);
    visited = (Boolean*)malloc(sizeof(Boolean) * courseNum);
    ans.course = (int*)malloc(sizeof(int) * courseNum);
    ans.term = (int*)malloc(sizeof(int) * courseNum);
    tmpAns = (int*)malloc(sizeof(int) * courseNum);
    level = (int*)malloc(sizeof(int) * courseNum);
    tmpTerm = (int*)malloc(sizeof(int) * courseNum);
    //初始化
    for (i = 0; i < courseNum; ++i) {
        visited[i] = FALSE;
        level[i] = 0;
    }
    ans.totalTerms = INT_MAX;
    ans.totalWeeks = INT_MAX;
    FindInDegree(g, inDegree);
    Queue q;
    InitQueue(&q);
    for (i = 0; i < courseNum; ++i) {
        if (!inDegree[i]) {
            EnQueue(&q, i);
        }
    }
    int v, count = 0, size, curLevel = 0;

    size = QueueLength(&q);
    while (!QueueEmpty(&q)) {
        if (size == 0) {
            size = QueueLength(&q);
            ++curLevel;
        }
        DeQueue(&q, &v);
        --size;
        ++count;
        level[v] = curLevel;
        ArcNode* j;
        for (j = g->Adjlist[v].firstarc; j != NULL; j = j->nextarc) {
            if (!(--inDegree[j->adjvex])) {
                EnQueue(&q, j->adjvex);
            }
        }
    }
    if (count < courseNum) {
        printf("课表组成的图结构中存在环，无法编排课表。\n");
        return FALSE;
    }
    /*测试代码
    for(i = 0; i < courseNum; ++i){
        printf("%d ",level[i]);
    }
    putchar('\n');
    */
    //选择合适的序列
    free(inDegree);
    inDegree = (int*)malloc(sizeof(int) * courseNum);
    FindInDegree(g, inDegree);
    DFS(g, 0);
    free(inDegree);
    free(visited);
    free(tmpTerm);
    return TRUE;
}